#include <time.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct bitnode {
    struct bitnode *left;
    struct bitnode *right;
    int value;
} bitnode;

void dump(int *arr, int length);
void init_array(int *arr, int length);
void shell_sort(int *arr, int length);
int bineary_search(int *arr, int key, int length);
void insert_tree(bitnode *node, int val);
node* create_search_tree(int *arr, int length);

int main() {
    srand(time(NULL));
    int length = 100;
    int arr[length];

    init_array(arr, length);
    dump(arr, length);

    int key = arr[rand() % length];
    printf("key is %d.\n", key);

    int result = bineary_search(arr, key, length);
    printf("\nbineary search result index: %d, value: %d.\n", result, arr[result]);

    return 0;
}

void dump(int *arr, int length) {
    if (!arr) {
        return;
    }

    int i;
    for (i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void init_array(int *arr, int length) {
    int i;
    for (i = 0; i < length; i++) {
        arr[i] = rand() % (length * 2);
    }

    shell_sort(arr, length);
}

void shell_sort(int *arr, int length) {
    int i, j, delta;
    int pivot;
    for (delta = length / 2; delta > 0; delta /= 2) {
        for (i = delta; i < length; i++) {
            pivot = arr[i];
            for (j = i - delta; j >= 0 && arr[j] > pivot; j -= delta) {
                arr[j + delta] = arr[j];
            }
            arr[j + delta] = pivot;
        }
    }
}

int bineary_search(int *arr, int key, int length) {
    int start = 0;
    int end = length;
    int mid;
    int result = -1;

    while (start < end) {
        mid = (start + end) / 2;
        if (arr[mid] > key) {
            end = mid;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            result = mid;
            break;
        }
    }

    return result;
}

void insert_tree(bitnode *node, int val) {
    if (!node || node->value == val) {
        return;
    }

    if (val > node->value) {
        insert_tree(node->right, val);
    } else {
        insert_tree(node->left, val);
    }
}
